#define  _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

void PrintArray(int* arr, int nums)
{
	for (int i = 0; i < nums; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Swap(int* buf1, int* buf2)
{
	int temp = *buf1;
	*buf1 = *buf2;
	*buf2 = temp;
}

int PartSort(int* arr, int left, int right)
{
	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		while (begin < end && arr[end] >= arr[keyi])
		{
			--end;
		}
		while (begin < end && arr[begin] <= arr[keyi])
		{
			++begin;
		}

		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[keyi], &arr[begin]);

	return begin;
}

void QuickSortNonR(int* arr, int nums)
{
	Queue Qu;
	QueueInit(&Qu);

	int begin = 0, end = nums - 1;
	if (begin < end)
	{
		QueuePush(&Qu, begin);
		QueuePush(&Qu, end);
	}

	while (!QueueEmpty(&Qu))
	{
		int left = QueueFront(&Qu);
		QueuePop(&Qu);
		int right = QueueFront(&Qu);
		QueuePop(&Qu);

		int keyi = PartSort(arr, left, right);
		if (left < keyi - 1)
		{
			QueuePush(&Qu, left);
			QueuePush(&Qu, keyi - 1);
		}
		if (keyi + 1 < right)
		{
			QueuePush(&Qu, keyi + 1);
			QueuePush(&Qu, right);
		}
	}

	QueueDestory(&Qu);
}